\documentclass{article}

\usepackage{gastex}
\usepackage[usenames]{color}
\usepackage[T1]{fontenc}

\renewcommand{\labelenumi}{\alph{enumi})}
\renewcommand{\labelenumii}{\arabic{enumii})}


\begin{document}

\textbf{Aufgabe:}\\
Schreiben Sie reguläre Ausdrücke für die folgenden Sprachen:

\begin{enumerate}
	\item 
	Die Menge aller Zeichenreihen aus Nullen und Einsen, die die Teilzeichenreihe $101$ nicht enthalten.
	
	\item
	Die Menge aller Zeichenreihen mit der gleichen Anzahl Einsen und Nullen, die so geformt sind, dass jedes Präfix weder zwei Einsen mehr als Nullen, noch zwei Nullen mehr als Einsen hat
	
	\item
	Die Menge aller Zeichenreihen aus Nullen und Einsen, deren Anzahl von Nullen durch 5 teilbar ist, und deren Anzahl von Einsen gerade.
\end{enumerate}

\textbf{Lösung:}
\begin{enumerate}
	\item 
	$0^{\ast}1^{\ast}(1000^{\ast}1)^{\ast}1^{\ast}0^{\ast} $


	\item Die Zeichen reihen müssen die selbe Anzahl Nullen und Einsen haben. Kein Präfix darf zwei Nullen mehr als Einsen oder andersherum haben. Das bedeutet:\\ Hat das Wort $\omega$ die Form $a_{1}a_{2}a_{3}...a_{k}...a_{n}$. Dann darf keine Teilzeichenreihe $a_{1}a_{2}a_{3}...a_{k}$ für $a \in \{1,2,...,n\}$ zwei Einsen mehr als Nullen oder zwei Nullen mehr als Einsen enthalten, also keine Teilzeichenreihe $...1000...$, $...0100...$ o.ä. bzw. $...0111...$, $...1011...$ o.ä..\\
	Audrücke die Teilzeichenreihen der Form $...111...$ oder $...000...$ "auslösen" haben ja meist eine ähnliche Form wie $...1^{\ast}...$ oder $...0^{\ast}...$. Um also längere Teilfolgen von Einsen oder Nullen zu verhindern paart man gleich von Anfang an Nullen und Einsen $(01)^{\ast}$. Dieser Ausdruck würde alle Zeichenreihen der Form $...010101010101....$ beschreiben. Das ist schon nah an der Lösung, da es alle Kriterien erfüllt: Selbe Anzahl Nullen und Einsen, und in keinem Präfix sind 2 mehr Nullen als Einsen oder anders herum. Jedoch gibt es ein große Menge Zeichenreihen, die diese Kriterien erfüllen, die mit diesem Ausdruck aber nicht beschrieben sind, nämlich solche der Form $...010101...10...01001010...$. Betrachtet man diese Zeichenreihe, stellt man fest, dass  selbst wenn beliebig oft $10$ in der Zeichenreihe auftritt, immernoch alle Kriterien erfüllt sind. Und damit hätte man dann auch noch den Teil gefunden, der die restlichen fehlenden Zeichenreihen beschreibt. Zusammen ergibt das dann:\\
	$((01)  + (10))^{\ast}$
\end{enumerate}

\end{document}